package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例 - Pow(x,n)
        Solution solution1 = new Solution();
        System.out.println("Pow(x,n):");
        System.out.println("2^10 = " + solution1.myPow(2.0, 10)); // 1024.0
        System.out.println("2.1^3 = " + solution1.myPow(2.1, 3)); // 9.261
        System.out.println("2^-2 = " + solution1.myPow(2.0, -2)); // 0.25

        // 测试用例 - 计算布尔二叉树的值
        Solution2 solution2 = new Solution2();
        System.out.println("\n计算布尔二叉树的值:");
        // 构造测试树: [2,1,3,null,null,0,1] -> OR(true, AND(false, true)) = true
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(1);
        System.out.println("示例: " + solution2.evaluateTree(root)); // true
    }

    // Pow(x,n)
    static class Solution {
        public double myPow(double x, int n) {
            long N = n;                 // 用 long 防止 -2^31 取反溢出
            if (N < 0) {
                x = 1.0 / x;            // 统一把负指数转为正指数
                N = -N;
            }
            return fastPow(x, N);       // 只处理非负幂
        }

        private double fastPow(double x, long n) {
            if (n == 0) return 1.0;
            double tmp = fastPow(x, n / 2);     // 递归算一半
            if ((n & 1) == 0) {                 // 偶数
                return tmp * tmp;
            } else {                             // 奇数
                return tmp * tmp * x;
            }
        }
    }

    // 计算布尔二叉树的值
    static class Solution2 {
        public boolean evaluateTree(TreeNode root) {
            // 叶子：0 -> false, 1 -> true
            if (root.left == null && root.right == null) {
                return root.val == 1;
            }
            // 后序：先算左右，再在父节点合并
            boolean left = evaluateTree(root.left);
            boolean right = evaluateTree(root.right);

            if (root.val == 2) {        // OR
                return left || right;
            } else {                    // AND（题面保证非叶为 2 或 3）
                return left && right;
            }
        }
    }

    // TreeNode 定义
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {}

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}